这道题像我这样的 蒟蒻都能一眼看出 式:
设 为 的前缀和,则有
Chihik's Blog
这道题像我这样的 dp 蒟蒻都能一眼看出 dp 式:
设 sum 为 c 的前缀和,则有
各位大佬都用的 wqs 二分,蒟蒻介绍一种简单方法。
dp 式很好列:
首先可以知道一个区间满足条件的必要条件是该区间的平均数大于等于 k 。
进一步可以发现这是一个充要条件。因为大于 k 的数一定能填补到小于 k 的数。
记一个合法的区间为 [l,r] ,sum 为 a 的前缀和。
显然是一道回文自动机板题。
设 L[i] 表示以 i 号点为左端点的最长回文串 , R[i] 表示以 i 号点为右端点的最长回文串。
L[i] 可以通过将回文串倒过来建自动机求得 , R[i] 可以直接用原回文串建自动机求得。
答案为所有的回文串组合-不相交的回文串组合。
记 cnt 为回文串个数 , 可以通过计算每个节点的回文串数量求得。
不相交的回文组合也比较好求,先算出以 i 为左端点和右端点的回文串数量 L[i] , R[i]。
令s=min(n,m)